#include "Student.h"
#include <iostream>
#include <cstdlib>
#include <vector>
#include <limits>


Student::Student()
{
   std_no = 0000000;
   major = 'N';
   GPA = 0.0;
};

Student::~Student()
{
  
};

Student::Student(int _std_no, char _major,
		 double _GPA)
{
  std_no = _std_no;
  major = _major;
  GPA = _GPA;
};

int Student::get_no()
{
  return std_no;
};

char Student::get_major()
{
  return major;
};

double Student::get_GPA()
{
  return GPA;
};

int Student::change_std_no(int new_no)
{
  std_no = new_no;
  return 0;
};

char Student::change_major(char new_major)
{
  major = new_major;
  return 0;
};

double Student::change_GPA(double new_GPA)
{
  GPA = new_GPA;
  return 0;
};

int Student::printout()
{
  std::cout << std_no << ' ' << major << ' ' << GPA << std::endl;
  return 0;
};

Heap::Heap()
{
  Student *A = NULL;
  n = 0;
};

Heap::Heap(Student *_A, int _n)
{
  A = new Student[_n];
  for(int i = 0; i < _n; i++)
    A[i] = _A[i];
  n = _n;
  for (int i = PARENT(_n - 1); i >= 0; i--)
    shiftdown(i);
};
  
Student* Heap::get_A()
{
  return A;
};

int Heap::shiftdown(int i)
{
  int lc = LEFTCHILD(i);
  if(lc >= n)
    return 0;
  int child = lc;
  int rc = RIGHTCHILD(i);
  if(rc < n && A[rc].get_major() > A[lc].get_major())
    child = rc;
  if (A[i].get_major() < A[child].get_major())
    {
      Student a;
      a = A[i];
      A[i] = A[child];
      A[child] = a;
      shiftdown(child);
    }
  else
    return 0;
};

int Heap::sort_m()
{
  int l = n;
  while( n > 0 )
    {
      Student a = A[0];
      A[0] = A[n-1];
      A[n-1] = a;
      n--;
      shiftdown(0);
    }
  n = l;
  return 0;
};


int Merge(Student *_A, int _p, int _q, int _r)
{
  int n1 = _q - _p + 1;
  int n2 = _r - _q;
  std::vector<Student> L(n1 + 1);
  std::vector<Student> R(n1 + 1);
  for (int i = 0; i < n1; i++)
    L[i] = _A[_p + i];
  for (int i = 0; i < n2; i++)
    R[i] = _A[_q + 1 + i];
  L[n1].change_GPA(10.0);
  R[n2].change_GPA(10.0);
  int i = 0;
  int j = 0;
  for(int k = _p; k < _r + 1; k++)
    {
      if ( L[i].get_GPA() <= R[j].get_GPA())
	{
	  _A[k] = L[i];
	  i++;
	}
      else
	{
	  _A[k] = R[j];
	  j++;
	}
    }
  return 0;
};

int Mergesort(Student *A, int _p, int _r)
{
  int* q = new int;
  if(_p < _r)
    {
      *q = (_p + _r) / 2;
      Mergesort(A, _p, *q);
      Mergesort(A, *q + 1, _r);
      Merge(A, _p, *q, _r);
    }
  return 0;
};

int arrange(Student *A, int begin_index, int end_index)
{
  Mergesort(A, begin_index, end_index);
  return 0;
};


